%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Header

\documentclass[17pt]{beamer}

\usepackage[english]{babel}
\usepackage{beamerthemesplit}
\usepackage{colortbl}
\usepackage{fdsymbol}
\usepackage{floatflt}
\usepackage[no-math]{fontspec}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{tikz}
\usepackage{wasysym}
\usepackage{xunicode}

\usetikzlibrary{shapes}

% When working on specific pages it is faster to generate just those pages.
% \usepackage[11-30]{pagesel}

\title{Haskell 101}
\author{pravnar@, javran@, mihaimaruseac@, ibobyr@, nicuveo@}
%\institute{Google}
\date{\small\today}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Customization

\input{theme}

\renewcommand{\(}[1]{\begin{columns}[#1]}
\renewcommand{\)}{\end{columns}}
\newcommand{\<}[1]{\begin{column}{#1}}
\renewcommand{\>}{\end{column}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Document

\begin{document}


% Set-up: have on screen while people are gathering
\togglefalse{showpagenumber}
\begin{frame}[fragile]
  \frametitle{Before we begin}
  \begin{code}[setup]
cd 00_setup && make
# Windows users: see setup.md
  \end{code}
\end{frame}


% Title frame

\begin{frame}[fragile]
  \titlepage
\end{frame}
\toggletrue{showpagenumber}
\setcounter{framenumber}{0}


\section{Intro}

\begin{frame}
  \frametitle{Today's menu}
  \({c}
  \<{.6\textwidth}
  \begin{center}
  \begin{itemize}
  \item 101
    \begin{itemize}
    \item Concepts and generalities
    \item Syntax overview
    \item Data structures
    \item Declaring functions
    \end{itemize}
  \end{itemize}
  \end{center}
  \>
  \<{.4\textwidth}
  \begin{center}
    \includegraphics[width=.5\textwidth]{img/whirlwind}
  \end{center}
  \>
  \)
\end{frame}

\begin{frame}
  \frametitle{Not today}
  \begin{center}
  \begin{itemize}
  \item Project environment
    \begin{itemize}
    \item Cabal? Stack?
    \item Hackage? Stackage?
    \item Haskell at Google?
    \end{itemize}
  \end{itemize}
  \begin{itemize}
  \item Advanced stuff
    \begin{itemize}
    \item Functors?
    \item Monads?
    \item Monad Transformers?
    \item \ldots
    \end{itemize}
  \end{itemize}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Prerequisites}
  \begin{center}
    \begin{itemize}
      \item Programming knowledge
        \begin{itemize}
          \item Imperative programming is enough
          \item Functional programming is a plus
        \end{itemize}
    \end{itemize}
  \end{center}
\end{frame}


\section{Haskell}

\begin{frame}
  \frametitle{What is Haskell?}
  \({c}
  \<{.5\textwidth}
  A programming language
  \begin{center}
    \begin{itemize}[<+->]
    \item General purpose
    \item Purely functional
    \item Lazily evaluated
    \item Strongly statically typed
    \end{itemize}
  \end{center}
  \>
  \<{.5\textwidth}
  \begin{center}
    \includegraphics[width=.5\textwidth]{img/haskell-logo}
  \end{center}
  \>
  \)
\end{frame}

\begin{frame}
  \frametitle{Haskell is NOT...}
  \begin{center}
    \begin{itemize}
    \item A silver bullet
    \item Only for category theorists
    \item<2-> Hard! \only<3->{Just different\ldots}
    \end{itemize}
  \end{center}
\end{frame}

% NOTE: Make sure you don't indent code blocks! Otherwise you get padding in
% the code blocks on the slide
\begin{frame}[fragile]
  \frametitle{Haskell is functional}
  \begin{minipage}[t][.2\textheight]{\textwidth}
    \begin{itemize}[<+->]
      \item Computation method is function application
      \item Contrast with variable assignment
      \item Lambda calculus $\rightarrow \ldots \rightarrow$ Haskell
    \end{itemize}
  \end{minipage}
  \begin{minipage}[c][.5\textheight]{\textwidth}
    \begin{center}
      \begin{onlyenv}<1->
        \begin{code}
sum [1 .. 10]
        \end{code}
      \end{onlyenv}
      \begin{onlyenv}<2->
        \begin{ccode}
int total = 0;
for (int i = 1; i < 10; i++)
  total += i;
        \end{ccode}
      \end{onlyenv}
  \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Functions are everywhere}
  \begin{minipage}[t][.2\textheight]{\textwidth}
    \begin{itemize}
    \item Similar to math
    \item<3-> \type{most common thing $\Rightarrow$ easiest to type}
  \end{itemize}
  \end{minipage}
  \begin{minipage}[c][.5\textheight]{\textwidth}
  \begin{center}
    \begin{onlyenv}<1>
      \begin{code}
f :: (*\type{Int}*) -> (*\type{Int}*)
f x = x + 1
      \end{code}
      \begin{align*}
        f    &: \mathbb{Z} \rightarrow \mathbb{Z}\\
        f(x) &= x + 1
      \end{align*}
    \end{onlyenv}
    \begin{onlyenv}<2->
      \begin{tabular}{ c | c }
        Math & Haskell \\\hline
        $f(x)$ & \texttt{f x} \\
        $f(x, y)$ & \texttt{f x y} \\
        $f(g(x))$ & \texttt{f (g x)} \\
        $f(g(x), h(y))$ & \texttt{f (g x) (h y)} \\
        $f(x) g(y)$ & \texttt{f x * g y}
      \end{tabular}
    \end{onlyenv}
  \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Everything is an expression}
  \begin{minipage}[t][.2\textheight]{\textwidth}
  \begin{itemize}
    \item No more statement vs expression differences
    \item<4-> Textual substitution as \type{model} for evaluation (reduction)
  \end{itemize}
  \end{minipage}
  \begin{minipage}[c][.5\textheight]{\textwidth}
  \begin{center}
    \begin{onlyenv}<1>
      \begin{ccode}
int a = 3;
int b = 5;
int c = f(a + b, a + 2 * b);
      \end{ccode}
    \end{onlyenv}
    \begin{onlyenv}<2>
      \begin{code}
1 + 2
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<3-5>
      \begin{code}
let a = 1
in  a + 2
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<4>
      \begin{code}[eval]
1 + 2
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<5>
      \begin{code}[eval]
3
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<6-7>
      \begin{code}
let a = if someBool then 1 else 0
in  a + 2
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<7>
      \begin{code}[eval]
(if someBool then 1 else 0) + 2
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<8-10>
      \begin{code}
let a = if someBool then 1 else 0
in  a + (let b = 2 in b)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<9>
      \begin{code}[eval]
(if someBool then 1 else 0) + (let b = 2 in b)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<10>
      \begin{code}[eval]
(if someBool then 1 else 0) + 2
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<11>
      \begin{code}
let offset = case color of
                 (*\cons{Red}*)   ->  0
                 (*\cons{Green}*) ->  8
                 (*\cons{Blue}*)  -> 16
in baseValue + offset
      \end{code}
    \end{onlyenv}
  \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Purely functional}
  \begin{minipage}[t][.2\textheight]{\textwidth}
  \begin{itemize}
    \item<1-> Do we have variables?
    \item<4-> {\color{google-r}No}: Everything is immutable
    \item<6-> No side effects\alt<7>{ \type{unless explicitly stated}}{!}
  \end{itemize}
  \end{minipage}
  \begin{minipage}[c][.5\textheight]{\textwidth}
  \begin{center}
    \begin{onlyenv}<1-3>
      \begin{code}
let a = 3
in  a = a + 1
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<2>
      \begin{code}[eval]
3 = 3 + 1
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<3>
      \begin{code}[eval]
3 = 4 -- this is (*\color{google-r}{bad}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<4-5>
      \begin{code}
let a = 3
in  a = a + 1 -- compile error
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<4>
      \begin{code}[eval]
3 = 4 -- compile error
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<5>
      \begin{code}
let a = 3
    b = a + 1
in b -- this is ok
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<6>
      \begin{code}
numberToWords :: (*\type{Int}*) -> String
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<7>
      \begin{code}
numberToWords :: (*\type{Int}*) -> String
readFile :: String -> IO String
      \end{code}
    \end{onlyenv}
  \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Purity...}
  \begin{code}
numberToWords :: (*\type{Int}*) -> String  -- (*\color{google-r}pure*) function
readFile :: String -> IO String -- (*\color{google-r}impure*) function
  \end{code}
\end{frame}

\begin{frame}[fragile]
  \frametitle{...and corruption}
  \begin{itemize}
    \item $\exists$ ~~\ict{f :: a -> IO a} ~~~~~{\small (from pure to impure)}
    \item $\nexists$ ~~\ict{f :: IO a -> a} ~~~~~{\small (from impure to pure)}
  \end{itemize}
  \begin{center}
    \uncover<2->{\type{IO} {\color{google-r}{corrupts}}.}\\
  \end{center}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Let's talk about evaluation order}
  \begin{minipage}[t][.2\textheight]{\textwidth}
    \begin{itemize}
      \item<1-> Which order for textual substitution?
      \item<4-> Are they always equivalent?
  \end{itemize}
  \end{minipage}
  \begin{minipage}[c][.5\textheight]{\textwidth}
  \begin{center}
    \begin{onlyenv}<1>
      \begin{code}
add x y = x + y
      \end{code}
      \begin{code}[eval]
add (12 + 8) (20 + 2)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<2>
      \begin{code}
add x y = x + y
      \end{code}
      \begin{code}[eval]
-- arguments first          | -- function body first
add (12 + 8) (20 + 2)       | add (12 + 8) (20 + 2)
                            |
                            |
                            |
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<3>
      \begin{code}
add x y = x + y
      \end{code}
      \begin{code}[eval]
-- arguments first          | -- function body first
add (12 + 8) (20 + 2)       | add (12 + 8) (20 + 2)
add 20 22                   | (12 + 8) + (20 + 2)
20 + 22                     | 20 + 22
42                          | 42
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<4>
      \begin{code}
add x y = x + y
      \end{code}
      \begin{code}[eval]
-- arguments first          | -- function body first
add (12 + 8) (20 + 2)       | add (12 + 8) (20 + 2)
add 20 22                   | (12 + 8) + (20 + 2)
20 + 22                     | 20 + 22
42                          | 42
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<5>
      \begin{code}
const x y = x
      \end{code}
      \begin{code}[eval]
-- arguments first          | -- function body first
const expr1 expr2           | const expr1 expr2
                            |
                            |
                            |
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<6>
      \begin{code}
const x y = x
      \end{code}
      \begin{code}[eval]
-- arguments first          | -- function body first
const (40 + 2) (20 + 2)     | const (40 + 2) (20 + 2)
const 42 22                 | (40 + 2)
42                          | 42
                            |
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<7>
      \begin{code}
const x y = x
      \end{code}
      \begin{code}[eval]
-- arguments first          | -- function body first
const (4+2) (error "Crash") | const (4+2) (error "Crash")
                            |
                            |
                            |
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<8>
      \begin{code}
const x y = x
      \end{code}
      \begin{code}[eval]
-- arguments first          | -- function body first
const (4+2) (error "Crash") | const (4+2) (error "Crash")
(*\color{red}error: Crash*)               | (4 + 2)
                            | 6
                            |
      \end{code}
    \end{onlyenv}
  \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Lazy evaluation}
  \begin{minipage}[t][.2\textheight]{\textwidth}
  \begin{itemize}
  \item Deferred expression evaluation
  \item Not used $\Rightarrow$ not computed
  \end{itemize}
  \end{minipage}
  \begin{minipage}[c][.5\textheight]{\textwidth}
  \begin{onlyenv}<2>
    \begin{center}
      QUIZ
    \end{center}
  \end{onlyenv}
  \begin{onlyenv}<3->
    \begin{center}
      \begin{ccode}
if (obj != nullptr && obj->value > 0)
      \end{ccode}
    \end{center}
  \end{onlyenv}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Laziness pros and cons}
  \begin{center}
    \begin{itemize}[<+->]
      \item[-] Memory pitfalls
      \item[-] IO and parallelism pitfalls
      \item[+] Huge optimizations
      \item[+] Greater expressivity (e.g. infinite structures)
    \end{itemize}
  \end{center}
  \begin{minipage}[c][.3\textheight]{\textwidth}
    \begin{center}
      \only<1-2>{Delayed computations (but escape hatches)}
      \only<3>{Equation reduction and short-circuiting}
      \begin{onlyenv}<4>
        \begin{code}
> naturalNumbers = [0,1..]
> squaredNumbers = map (^2) naturalNumbers
> take 5 squaredNumbers
[0,1,4,9,16]
        \end{code}
      \end{onlyenv}
    \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Programming languages and types}
  \begin{minipage}[t][.3\textheight]{\textwidth}
    \begin{itemize}
      \item<1-> Untyped
      \item<2-> Dynamically typed
      \item<3-> Statically typed
      \item<4-> Haskell: strongly statically typed with type inference
    \end{itemize}
  \end{minipage}
  \begin{minipage}[c][.4\textheight]{\textwidth}
  \begin{center}
    \begin{onlyenv}<1>
      \begin{ccode}[asm]
mov rax, r8
mov rbx, r9
add rax, rbx
      \end{ccode}
    \end{onlyenv}
    \begin{onlyenv}<2>
      \begin{pycode}
def add(a, b):
  return a + b
      \end{pycode}
    \end{onlyenv}
    \begin{onlyenv}<3>
      \begin{ccode}
int add(int a, int b) {
  return a + b;
}
      \end{ccode}
    \end{onlyenv}
    \begin{onlyenv}<4>
      \begin{code}
-- add :: Int -> Int -> Int
add x y = x + y
      \end{code}
    \end{onlyenv}
  \end{center}
  \end{minipage}
\end{frame}

\section{Haskell syntax and simple types}

\begin{frame}[fragile]
  \frametitle{GHCi and Haskell}
  \begin{minipage}[t][.3\textheight]{\textwidth}
    \begin{itemize}
      \item<1-> Read-Eval-Print-Loop interpreter
      \item<1-> Your new best friend
      \item<1-> Fast iteration time
      \item<2-> Desktop calculator
      \item<3-> Type inference using \ic{:type} (\ic{:t})
      \item<3-> $\ldots$
    \end{itemize}
  \end{minipage}
  \begin{minipage}[c][.45\textheight]{\textwidth}
  \begin{center}
    \begin{onlyenv}<2>
      \begin{code}
Prelude> 2 + 3
5
Prelude> sqrt (3 ^ 2 + 4 ^ 2)
5.0
      \end{code}
    \end{onlyenv}
  \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Basic Haskell types}
  \begin{center}
    \begin{code}
Prelude> :t anInt
anInt :: Int
Prelude> :t aDouble
aDouble :: Double
Prelude> :t 'a'
'a' :: Char
Prelude> :t "this is a string"
"this is a string" :: String -- or (*\type{[Char]}*)
Prelude> :t [anInt, anInt + 2, 2 * anInt]
[anInt, anInt + 2, 2 * anInt] :: [Int]
Prelude> :t (anInt, aDouble)
(anInt, aDouble) :: (Int, Double)
    \end{code}
  \end{center}
\end{frame}


\section{Function types}

\begin{frame}
  \frametitle{Function types}
  \begin{center}
    \begin{tabular}{ l c r }
      \uncover<1->{\inlinecode{f}     & \inlinecode{::} & \inlinecode{Int -> Int -> Int}} \\
      \multicolumn{3}{l}{\uncover<2->{\inlinecode{f x y = x + y}}} \\
      \uncover<3->{\inlinecode{f 1 2} & \inlinecode{::} & \inlinecode{              Int}} \\
      \multicolumn{3}{l}{\uncover<4->{\inlinecode{3}}}
    \end{tabular}
  \end{center}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Polymorphism}
  \begin{minipage}[t][.2\textheight]{\textwidth}
    \begin{itemize}
      \item<1-> What is the type of \ic{length} below?
      \item<2-> \ict{length :: [a] -> Int}
      \item<3-> \ict{a} is a type variable: stand-in for \type{any} type
    \end{itemize}
  \end{minipage}
  \begin{minipage}[c][.5\textheight]{\textwidth}
  \begin{center}
    \begin{code}
Prelude> length [1 .. 5]
5
Prelude> length "this is some string"
19
    \end{code}
  \end{center}
  \end{minipage}
\end{frame}

\begin{frame}
  \frametitle{First letter rule}
  \begin{center}
    \begin{tabular}{ l r r }
      Context & Capital letter & Lowercase letter\\
      \hline\hline
              & Fixed type                & Type variable\\
      Type    & (\ict{Int}, \ldots)       & (\ict{a}, \ldots) \\
      \hline
              &                           & Functions,\\
      Value   &      ????                 & arguments,\\
              &                           & names, \ldots
    \end{tabular}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Searching for functions}
  \begin{center}
    \begin{itemize}
      \item Type of a function determine what the function can do?
      \item There can be only one \ict{a -> b -> a} function
      \item (modulo assumptions)
      \item<2-> Can we get to the function given the type signature?
      \item<3-> \texttt{djinn}: Generate Haskell code from a type
      \item<4-> Hoogle, Hayoo
    \end{itemize}
  \end{center}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Recursive functions}
  \begin{minipage}[t][.2\textheight]{\textwidth}
    \begin{itemize}
      \item<1-> Haskell code is immutable
      \item<1-> But our code needs variables
      \item<2-> Recursion is our friend
    \end{itemize}
  \end{minipage}
  \begin{minipage}[c][.5\textheight]{\textwidth}
  \begin{center}
    \begin{onlyenv}<1>
      \begin{code}
sumList :: [Int] -> Int
sumList list = ???
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<2>
      \begin{code}
sumList :: [Int] -> Int
sumList list =
  if null list
  then 0
  else head list + sumList (tail list)
      \end{code}
    \end{onlyenv}
  \end{center}
  \end{minipage}
\end{frame}


\section{Codelab - 01}

\begin{frame}
  \frametitle{Codelab - \ic{01_functions}}
  \begin{description}
    \item[directory]: \ic{01_functions}
    \item[change]: \ic{src/Codelab.hs} \\
      (replace \ic{codelab} with implementation)
    \item[check with]: \ic{make}
  \end{description}
\end{frame}


\section{Data structures}

\begin{frame}[fragile]
  \frametitle{Type synonyms}
  \begin{onlyenv}<1>
    \begin{code}
type (*\type{Point}*)   = (Int, Int)  -- tuple
    \end{code}
  \end{onlyenv}
  \begin{onlyenv}<2>
    \begin{code}
type (*\type{Point}*)   = (Int, Int)  -- tuple
type (*\type{Polygon}*) = [(*\type{Point}*)]     -- list
    \end{code}
  \end{onlyenv}
  \begin{onlyenv}<3>
    \begin{code}
type (*\type{Point}*)   = (Int, Int)  -- tuple
type (*\type{Polygon}*) = [(*\type{Point}*)]     -- list
type (*\type{Map}*) (*\tvar{k}*) (*\tvar{v}*) = [((*\tvar{k}*), (*\tvar{v}*))]    -- type parameters
    \end{code}
  \end{onlyenv}
\end{frame}

\begin{frame}
  \frametitle{Immutable data structures...}
  \begin{center}
    {~ What do they consist of?}
    \begin{itemize}
      \item<2-> No private members...
      \item<3-> No modifiers...
      \item<4-> No methods...
      \item<5-> Only \tvar{constructors}
    \end{itemize}
  \end{center}
\end{frame}

\begin{frame}[fragile]
  \frametitle{C++ data types}
  \begin{minipage}{.5\textwidth}
  \begin{ccode}
class C {
 public:
  C(string name, int age);
  virtual ~C ();
  string getName();
  int getAge();
  int getAgeIn(int n);
  void setName(string name);
  void setAge(int age);
 private:
  string name;
  int age;
};
  \end{ccode}
  \end{minipage}
  \hspace{.1\textwidth}
  \begin{minipage}[r]{.3\textwidth}
  \tikzstyle{blk} = [draw=black,
    minimum width=3.5cm,
    minimum height=0.8cm,
    node distance=0.8cm]
  \begin{tikzpicture}
    \node[blk] (name) {\ic{name}};
    \node[blk, below of=name] (age) {\ic{age}};
    \node[blk, below of=age] (C) {\ic{C()}};
    \node[blk, below of=C] (CC) {\ic{~C()}};
    \node[blk, below of=CC] (getName) {\ic{getName()}};
    \node[blk, below of=getName] (getAge) {\ic{getAge()}};
    \node[blk, below of=getAge] (getAgeIn) {\ic{getAgeIn()}};
    \node[blk, below of=getAgeIn] (setName) {\ic{setName()}};
    \node[blk, below of=setName] (setAge) {\ic{setAge()}};
  \end{tikzpicture}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Haskell data types}
  \begin{minipage}[t][.4\textheight]{\textwidth}
  \begin{code}
data C = MakeOneC String Int
(*\\*)
person :: C
person = MakeOneC "John Smith" 42
  \end{code}
  \end{minipage}
  \begin{minipage}[t][.4\textheight]{\textwidth}
  \tikzstyle{blk0} = [draw=black,minimum height=0.8cm]
  \tikzstyle{blk} = [blk0,minimum width=0.8cm]
  \begin{tikzpicture}
    \node[blk0, minimum width=1.4cm] (c) {\ic{MakeOneC}};
    \node[blk, right of=c, node distance=1.45cm] (p) {};
    \node[blk, right of=p, node distance=0.8cm] (q) {};
    \node[above of=p] (s0) {};
    \node[blk0, right of=s0, node distance=2.5cm] (s) {\ic{"John Smith"}};
    \path[draw, -latex] (p.center) -- (s0.center) -- (s.west);
    \node[below of=q] (s1) {};
    \node[blk0, right of=s1, node distance=1.8cm] (i) {\ic{42}};
    \path[draw, -latex] (q.center) -- (s1.center) -- (i.west);
  \end{tikzpicture}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{The almighty "data" keyword}
  \begin{minipage}[t][.4\textheight]{\textwidth}
    \begin{onlyenv}<1>
      \begin{code}
data (*\type{Bool}*)    = (*\cons{False}*) | (*\cons{True}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<2>
      \begin{code}
data (*\type{Bool}*)    = (*\cons{False}*) | (*\cons{True}*)
data (*\type{None}*)    = (*\cons{None}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<3>
      \begin{code}
data (*\type{Bool}*)    = (*\cons{False}*) | (*\cons{True}*)
data (*\type{None}*)    = (*\cons{None}*)
data (*\type{Minutes}*) = (*\cons{Minutes}*) (*\type{Int}*)
      \end{code}
    \end{onlyenv}
  \end{minipage}
  \begin{minipage}[c][.3\textheight]{\textwidth}
    \begin{center}
      \begin{onlyenv}<1>
        \begin{code}[types]
(*\cons{True}*)  :: (*\type{Bool}*)
(*\cons{False}*) :: (*\type{Bool}*)
        \end{code}
      \end{onlyenv}
      \begin{onlyenv}<2>
        \begin{code}[types]
(*\cons{None}*) :: (*\type{None}*)
        \end{code}
      \end{onlyenv}
      \begin{onlyenv}<3>
        \begin{code}[types]
(*\cons{Minutes}*)    :: (*\type{Int}*) -> (*\type{Minutes}*)
(*\cons{Minutes}*) 42 ::        (*\type{Minutes}*)
        \end{code}
      \end{onlyenv}
    \end{center}
  \end{minipage}
\end{frame}

\begin{frame}
  \frametitle{First letter rule}
  \begin{center}
    \begin{tabular}{ l r r }
      Context & Capital letter & Lowercase letter\\
      \hline\hline
              & Fixed type                  & Type variable\\
      Type    & (\ict{Int}, \ldots)         & (\ict{a}, \ldots) \\
      \hline
              & Constructors                & Functions,\\
      Value   & (\cons{True}, \cons{False}) & arguments,\\
              &                             & names, \ldots
    \end{tabular}
  \end{center}
\end{frame}


\section{Pattern matching}

\begin{frame}[fragile]
  \frametitle{Not}
  \begin{minipage}[t][.4\textheight]{\textwidth}
    \begin{onlyenv}<1>
      \begin{code}
data (*\type{Bool}*) = (*\cons{False}*) | (*\cons{True}*)
(*\\*)
not :: (*\type{Bool}*) -> (*\type{Bool}*)
not x = ???
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<2-3>
      \begin{code}
data (*\type{Bool}*) = (*\cons{False}*) | (*\cons{True}*)
(*\\*)
not :: (*\type{Bool}*) -> (*\type{Bool}*)
not x = if x then (*\cons{False}*) else (*\cons{True}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<4>
      \begin{code}
data (*\type{Bool}*) = (*\cons{False}*) | (*\cons{True}*)
(*\\*)
not :: (*\type{Bool}*) -> (*\type{Bool}*)
not (*\cons{True}*)  = (*\cons{False}*)
not (*\cons{False}*) = (*\cons{True}*)
      \end{code}
    \end{onlyenv}
  \end{minipage}
  \begin{minipage}[c][.3\textheight]{\textwidth}
    \begin{center}
      \only<3>{Only for built-in type(s)}
      \only<4->{\#PatternMatching}
    \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{And}
  \begin{minipage}[t][.4\textheight]{\textwidth}
    \begin{onlyenv}<1>
      \begin{code}
data (*\type{Bool}*) = (*\cons{False}*) | (*\cons{True}*)
(*\\*)
(&&) :: (*\type{Bool}*) -> (*\type{Bool}*) -> (*\type{Bool}*)
x && y = ???
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<2-3>
      \begin{code}
data (*\type{Bool}*) = (*\cons{False}*) | (*\cons{True}*)
(*\\*)
(&&) :: (*\type{Bool}*) -> (*\type{Bool}*) -> (*\type{Bool}*)
x && y = if x
  then (if y then (*\cons{True}*) else (*\cons{False}*))
  else (*\cons{False}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<4>
      \begin{code}
data (*\type{Bool}*) = (*\cons{False}*) | (*\cons{True}*)
(*\\*)
(&&) :: (*\type{Bool}*) -> (*\type{Bool}*) -> (*\type{Bool}*)
(*\cons{True}*)  && (*\cons{True}*)  = (*\cons{True}*)
(*\cons{True}*)  && (*\cons{False}*) = (*\cons{False}*)
(*\cons{False}*) && (*\cons{True}*)  = (*\cons{False}*)
(*\cons{False}*) && (*\cons{False}*) = (*\cons{False}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<5-7>
      \begin{code}
data (*\type{Bool}*) = (*\cons{False}*) | (*\cons{True}*)
(*\\*)
(&&) :: (*\type{Bool}*) -> (*\type{Bool}*) -> (*\type{Bool}*)
(*\cons{True}*) && (*\cons{True}*) = (*\cons{True}*)
x    && y    = (*\cons{False}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<8>
      \begin{code}
data (*\type{Bool}*) = (*\cons{False}*) | (*\cons{True}*)
(*\\*)
(&&) :: (*\type{Bool}*) -> (*\type{Bool}*) -> (*\type{Bool}*)
(*\cons{True}*) && y = y
x    && y = (*\cons{False}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<9>
      \begin{code}
data (*\type{Bool}*) = (*\cons{False}*) | (*\cons{True}*)
(*\\*)
(&&) :: (*\type{Bool}*) -> (*\type{Bool}*) -> (*\type{Bool}*)
(*\cons{True}*) && y = y
_    && _ = (*\cons{False}*)
      \end{code}
    \end{onlyenv}
  \end{minipage}
  \begin{minipage}[c][.3\textheight]{\textwidth}
    \begin{center}
      \only<3>{Only for built-in type(s)}
      \only<6>{Can you spot a problem?}
      \only<7>{Eager in the second argument :(}
    \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Deconstructors?}
  \begin{minipage}[t][.4\textheight]{\textwidth}
    \begin{onlyenv}<1>
      \begin{code}
data (*\type{Minutes}*) = (*\cons{Minutes}*) (*\type{Int}*)
(*\\*)
add :: (*\type{Minutes}*) -> (*\type{Minutes}*) -> (*\type{Minutes}*)
add mx my = ???
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<2-3>
      \begin{code}
data (*\type{Minutes}*) = (*\cons{Minutes}*) (*\type{Int}*)
(*\\*)
add :: (*\type{Minutes}*) -> (*\type{Minutes}*) -> (*\type{Minutes}*)
add mx my = mx + my
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<4>
      \begin{code}
data (*\type{Minutes}*) = (*\cons{Minutes}*) (*\type{Int}*)
(*\\*)
add :: (*\type{Minutes}*) -> (*\type{Minutes}*) -> (*\type{Minutes}*)
add ((*\cons{Minutes}*) x) ((*\cons{Minutes}*) y) = ???
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<5>
      \begin{code}
data (*\type{Minutes}*) = (*\cons{Minutes}*) (*\type{Int}*)
(*\\*)
add :: (*\type{Minutes}*) -> (*\type{Minutes}*) -> (*\type{Minutes}*)
add ((*\cons{Minutes}*) x) ((*\cons{Minutes}*) y) = (*\cons{Minutes}*) (x + y)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<6>
      \begin{code}
data (*\type{Minutes}*) = (*\cons{Minutes}*) (*\type{Int}*)
(*\\*)
add :: (*\type{Minutes}*) -> (*\type{Minutes}*) -> (*\type{Minutes}*)
add ((*\cons{Minutes}*) x) ((*\cons{Minutes}*) y) = (*\cons{Minutes}*) $ x + y
      \end{code}
    \end{onlyenv}
  \end{minipage}
  \begin{minipage}[c][.3\textheight]{\textwidth}
    \begin{center}
      \only<3>{Needs overload for \ic{+} to work on \ict{Minutes} directly!}
    \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Record syntax}
  \begin{minipage}[t][0.4\textheight]{\textwidth}
    \begin{onlyenv}<1>
      \begin{code}
data (*\type{User}*) = (*\cons{User}*) (*\type{String}*) (*\type{String}*) (*\type{Int}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<2->
      \begin{code}
data (*\type{User}*) = (*\cons{User}*) {
  userFirstName :: (*\type{String}*),
  userLastName  :: (*\type{String}*),
  userAge       :: (*\type{Int}*)
}
      \end{code}
    \end{onlyenv}
  \end{minipage}
  \begin{onlyenv}<1-2>
    \begin{code}[types]
(*\cons{User}*)          :: (*\type{String}*) -> (*\type{String}*) -> (*\type{Int}*) -> (*\type{User}*)
    \end{code}
  \end{onlyenv}
  \begin{onlyenv}<3>
    \begin{code}[types]
(*\cons{User}*)          :: (*\type{String}*) -> (*\type{String}*) -> (*\type{Int}*) -> (*\type{User}*)
userFirstName :: (*\type{User}*) -> (*\type{String}*)
userLastName  :: (*\type{User}*) -> (*\type{String}*)
userAge       :: (*\type{User}*) -> (*\type{Int}*)
    \end{code}
  \end{onlyenv}
\end{frame}


\section{Codelab - 02}

\begin{frame}
  \frametitle{Codelab - \ic{02_datatypes}}
  \begin{description}
    \item[directory]: \ic{02_datatypes}
    \item[change]: \ic{src/Codelab.hs} \\
      (replace \ic{codelab} with implementation)
    \item[check with]: \ic{make}
  \end{description}
\end{frame}


\section{Advanced data definition}

\begin{frame}[fragile]
  \frametitle{The almighty "data" keyword. Continued}
  \begin{minipage}[t][.4\textheight]{\textwidth}
    \begin{onlyenv}<1>
      \begin{code}
data (*\type{Bool}*)    = (*\cons{False}*) | (*\cons{True}*)
data (*\type{None}*)    = (*\cons{None}*)
data (*\type{Minutes}*) = (*\cons{Minutes}*) (*\type{Int}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<2>
      \begin{code}
data (*\type{Bool}*)    = (*\cons{False}*) | (*\cons{True}*)
data (*\type{None}*)    = (*\cons{None}*)
data (*\type{Minutes}*) = (*\cons{Minutes}*) (*\type{Int}*)
data (*\type{Maybe}*) (*\tvar{a}*) = (*\cons{Nothing}*) | (*\cons{Just}*) (*\tvar{a}*)
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<3-4>
      \begin{code}
data (*\type{Bool}*)    = (*\cons{False}*) | (*\cons{True}*)
data (*\type{None}*)    = (*\cons{None}*)
data (*\type{Minutes}*) = (*\cons{Minutes}*) (*\type{Int}*)
data (*\type{Maybe}*) (*\tvar{a}*) = (*\cons{Nothing}*) | (*\cons{Just}*) (*\tvar{a}*)
data (*\type{List}*) (*\tvar{a}*)  = (*\cons{Nil}*) | (*\cons{Cell}*) (*\tvar{a}*) ((*\type{List}*) (*\tvar{a}*))
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<5-6>
      \begin{code}
data (*\type{Bool}*)    = (*\cons{False}*) | (*\cons{True}*)
data (*\type{None}*)    = (*\cons{None}*)
data (*\type{Minutes}*) = (*\cons{Minutes}*) (*\type{Int}*)
data (*\type{Maybe}*) (*\tvar{a}*) = (*\cons{Nothing}*) | (*\cons{Just}*) (*\tvar{a}*)
data (*\type{List}*) (*\tvar{a}*)  = (*\cons{Nil}*) | (*\cons{Cell}*) (*\tvar{a}*) ((*\type{List}*) (*\tvar{a}*))
data [(*\tvar{a}*)]     = [] | ((*\tvar{a}*):[(*\tvar{a}*)])
      \end{code}
    \end{onlyenv}
  \end{minipage}
  \begin{minipage}[c][.3\textheight]{\textwidth}
    \begin{center}
      \begin{onlyenv}<2>
        \begin{code}[types]
(*\cons{Nothing}*) ::      (*\type{Maybe}*) (*\tvar{a}*)
(*\cons{Just}*)    :: (*\tvar{a}*) -> (*\type{Maybe}*) (*\tvar{a}*)
(*\cons{Just}*) 42 ::      (*\type{Maybe}*) (*\type{Int}*)
        \end{code}
      \end{onlyenv}
      \begin{onlyenv}<3>
        \begin{code}[types]
                  (*\cons{Nil}*) ::      (*\type{List}*) (*\tvar{a}*)
                 (*\cons{Cell}*) :: (*\tvar{a}*) -> (*\type{List}*) (*\tvar{a}*) -> (*\type{List}*) (*\tvar{a}*)
(*\cons{Cell}*) 0 ((*\cons{Cell}*) 1 ((*\cons{Nil}*))) :: (*\type{List}*) (*\type{Int}*)
        \end{code}
      \end{onlyenv}
      \begin{onlyenv}<4>
        \begin{code}[types]
                  (*\cons{Nil}*) ::      (*\type{List}*) (*\tvar{a}*)
                 (*\cons{Cell}*) :: (*\tvar{a}*) -> (*\type{List}*) (*\tvar{a}*) -> (*\type{List}*) (*\tvar{a}*)
(*\cons{Cell}*) 0 $ (*\cons{Cell}*) 1 $ (*\cons{Nil}*) :: (*\type{List}*) (*\type{Int}*)
        \end{code}
      \end{onlyenv}
      \begin{onlyenv}<5>
        \begin{code}[types]
        [] :: [(*\tvar{a}*)]
       (:) :: (*\tvar{a}*) -> [(*\tvar{a}*)] -> [(*\tvar{a}*)]
0 : 1 : [] :: [(*\type{Int}*)]
        \end{code}
      \end{onlyenv}
      \begin{onlyenv}<6>
        \begin{code}[types]
        [] :: [(*\tvar{a}*)]
       (:) :: (*\tvar{a}*) -> [(*\tvar{a}*)] -> [(*\tvar{a}*)]
    [0, 1] :: [(*\type{Int}*)]
        \end{code}
      \end{onlyenv}
    \end{center}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Length}
  \begin{minipage}[t][.4\textheight]{\textwidth}
    \begin{onlyenv}<1>
      \begin{code}
data [(*\tvar{a}*)] = [] | ((*\tvar{a}*):[(*\tvar{a}*)])
(*\\*)
length :: [(*\tvar{a}*)] -> (*\type{Int}*)
length l = ???
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<2>
      \begin{code}
data [(*\tvar{a}*)] = [] | ((*\tvar{a}*):[(*\tvar{a}*)])
(*\\*)
length :: [(*\tvar{a}*)] -> (*\type{Int}*)
length []     = ???
length (x:xs) = ???
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<3>
      \begin{code}
data [(*\tvar{a}*)] = [] | ((*\tvar{a}*):[(*\tvar{a}*)])
(*\\*)
length :: [(*\tvar{a}*)] -> (*\type{Int}*)
length []     = 0
length (x:xs) = ???
      \end{code}
    \end{onlyenv}
    \begin{onlyenv}<4>
      \begin{code}
data [(*\tvar{a}*)] = [] | ((*\tvar{a}*):[(*\tvar{a}*)])
(*\\*)
length :: [(*\tvar{a}*)] -> (*\type{Int}*)
length []     = 0
length (_:xs) = 1 + length xs
      \end{code}
    \end{onlyenv}
  \end{minipage}
  \begin{minipage}[c][.3\textheight]{\textwidth}
    \begin{center}
      \only<4>{\#Recursion}
    \end{center}
  \end{minipage}
\end{frame}


\section{Codelab - 03}

\begin{frame}
  \frametitle{Codelab - \ic{03_lists}}
  \begin{description}
    \item[directory]: \ic{03_lists}
    \item[change]: \ic{src/Codelab.hs} \\
      (replace \ic{codelab} with implementation)
    \item[check with]: \ic{make}
  \end{description}
\end{frame}


\section{Curried functions, partial application}

\begin{frame}[fragile]
  \frametitle{Curried functions, partial application}
  \begin{onlyenv}<1>
    \begin{code}
(*\\*)
 f      :: Int ->   Int -> Int
(*\\*)
(*\\*)
(*\\*)
    \end{code}
  \end{onlyenv}
  \begin{onlyenv}<2>
    \begin{code}
 f      :: Int -> ( Int -> Int )
 f      :: Int ->   Int -> Int
(*\\*)
(*\\*)
(*\\*)
    \end{code}
  \end{onlyenv}
  \begin{onlyenv}<3>
    \begin{code}
 f      :: Int -> ( Int -> Int )
 f      :: Int ->   Int -> Int
 f 1    ::          Int -> Int
(*\\*)
(*\\*)
    \end{code}
  \end{onlyenv}
  \begin{onlyenv}<4>
    \begin{code}
 f      :: Int -> ( Int -> Int )
 f      :: Int ->   Int -> Int
 f 1    ::          Int -> Int
(*\\*)
(f 1) 2 ::                 Int
    \end{code}
  \end{onlyenv}
  \begin{onlyenv}<5>
    \begin{code}
 f      :: Int -> ( Int -> Int )
 f      :: Int ->   Int -> Int
 f 1    ::          Int -> Int
 f 1  2 ::                 Int
(f 1) 2 ::                 Int
    \end{code}
  \end{onlyenv}
\end{frame}

\begin{frame}
  \frametitle{Quiz!}
  \begin{minipage}[c][.4\textheight]{\textwidth}
    \begin{center}
      \begin{tabular}{ r c l }
        \alt<3->{\ic{   map}}{\ic{???}} & \ic{::} & \ict{(a -> b) -> [a] -> [b]}
        \\\uncover<5->{\alt<6->{\ic{filter}}{\ic{??????}} & \ic{::} & \ict{(a -> Bool) -> [a] -> [a]} }
        \\\uncover<7->{\ic{(.)}                           & \ic{::} & \ict{(b -> c) -> (a -> b) -> (a -> c)} }
      \end{tabular}
    \end{center}
  \end{minipage}
  \begin{minipage}[c][.3\textheight]{\textwidth}
    \begin{center}
      \begin{onlyenv}<2-3>
        \begin{tabular}{ c l }
          \ict{(a -> b)} & \small function from type A to type B\\
          \ict{[a]}      & \small list of values of type A\\
          \ict{[b]}      & \small list of values of type B
        \end{tabular}
      \end{onlyenv}
      \begin{onlyenv}<4>
        \begin{tabular}{ r l }
          \ict{add2 x = x + 2}\\
          \ict{map add2 [1, 2, 3]}           & \small direct call, result \ict{[3, 4, 5]}\\
          \ict{map (\\x -> x + 2) [1, 2, 3]} & \small lambda function (anonymous)
        \end{tabular}
      \end{onlyenv}
      \only<8>{\small $(f \circ g) (x) = f(g(x))$}
      \begin{onlyenv}<9>
        \begin{tabular}{ r c l c r c c c l}
          &      & \bi{\ic{show}} &\ic{::}& \type{\ic{Stuff}} &\ic{->}& \ic{String} &       &          \\
          \bi{\ic{length}} &      &                &\ic{::}&                   &       & \ic{String} &\ic{->}& \ic{Int} \\
          \bi{\ic{length}} &\ic{.}& \bi{\ic{show}} &\ic{::}& \type{\ic{Stuff}} &       &             &\ic{->}& \ic{Int} \\
        \end{tabular}
      \end{onlyenv}
      \only<10>{\inlinecode{cat input | grep token | sed stuff | tee output}}
    \end{center}
  \end{minipage}
\end{frame}

\begin{frame}
  \frametitle{Quiz with a vengeance!}
  \begin{center}
    \begin{tabular}{ r c l }
      \only<1-2> {\ic{?????}}
      \only<3->{\ic{foldl}} & \ic{::} & \ict{(a -> b -> a) -> a -> [b] -> a}
    \end{tabular}
    \begin{onlyenv}<2->
      ~\\~\\~\\
      \begin{tabular}{ c l }
        \ict{(a -> b -> a)} & \small combines accumulator and value\\
        \ict{a}             & \small initial accumulator\\
        \ict{[b]}           & \small list of values\\
        \ict{a}             & \small result
      \end{tabular}
    \end{onlyenv}
    \begin{onlyenv}<4->
      ~\\~\\~\\
      \small "reduce"
    \end{onlyenv}
  \end{center}
\end{frame}


\section{Codelab - 04}

\begin{frame}
  \frametitle{Codelab - \ic{04_abstractions}}
  \begin{description}
    \item[directory]: \ic{04_abstractions}
    \item[change]: \ic{src/Codelab.hs} \\
      (replace \ic{codelab} with implementation)
    \item[check with]: \ic{make}
  \end{description}
\end{frame}


\begin{frame}
  \frametitle{The end of the theoretical part!}
  \begin{center}
    Questions?
  \end{center}
\end{frame}


\section{Links}

\begin{frame}
  \frametitle{Links}
  \begin{itemize}
  \item \href{https://tryhaskell.org}{tryhaskell.org}
  \item \href{https://learnyouahaskell.com}{learnyouahaskell.com}
  \item \href{https://book.realworldhaskell.org}{book.realworldhaskell.org}
  \item \href{http://haskellbook.com}{haskellbook.com}
  \item \href{https://www.haskell.org/hoogle/}{haskell.org/hoogle/}
  \item \href{https://dev.to/stereobooster/pragmatic-types-type-systems-vs-tests-4k3e}{Pragmatic types: types vs tests}
  \item \href{https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf}{Why functional programming matters}
  \end{itemize}
\end{frame}


\section{Codelab - 05}

\begin{frame}
  \frametitle{Codelab - \ic{05_maybe}}
  \begin{description}
    \item[directory]: \ic{05_maybe}
    \item[change]: \ic{src/Codelab.hs} \\
      (replace \ic{codelab} with implementation)
    \item[check with]: \ic{make}
  \end{description}
\end{frame}


\section{Codelab - 06 (bonus)}

\begin{frame}
  \frametitle{Codelab - \ic{06_rps} (bonus)}
  \begin{description}
    \item[directory]: \ic{06_rps}
    \item[change]: \ic{src/Codelab.hs} \\
      (replace \ic{codelab} with implementation)
    \item[check with]: \ic{make}
  \end{description}
\end{frame}


\section{The end}

\begin{frame}
  \frametitle{The end!}
  \begin{center}
    Questions?
  \end{center}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% End

\end{document}
